package org.marverse.language

import scala.collection.mutable.{HashMap, MultiMap, Set}
import scala.collection.immutable.{TreeSet}

sealed trait Associativity
final case object LeftAssoc extends Associativity
final case object RightAssoc extends Associativity
final case object NoAssoc extends Associativity

class ExtensibleParser[T, R] extends Parser[T, R] {

  class Production(val priority: Int, 
                   val assoc: Associativity,
                   val inner: Parser[_ >: T, _ <: R])
  extends Ordered[Production] {
	override def compare(that: Production) = priority.compare(that.priority)
    def pop = ExtensibleParser.this
    val leftMost = inner.leftMost
    val rightMost = inner.rightMost
      
    leftMost match {
      case rp: Reference if rp.pop == pop => rp.amLeftMost = true; rp.priority = priority + 1
      case _ =>
    }
    if (leftMost != rightMost)
      rightMost match {
        case rp: Reference if rp.pop == pop => rp.priority =
          if (assoc == RightAssoc) priority else priority + 1
        case _ => 
      }
  }
  def prod(priority: Int, 
           assoc: Associativity,
           inner: Parser[_ >: T, _ <: R]) {
    productions.add(priority, new Production(priority, assoc, inner)) 
  }

  // not thread-safe, replaceLeftMost should be thread-local
  private var replaceLeftMost: Option[AcceptingResult[T, R]] = None
  class Reference extends Parser[T, R] {
    def pop = ExtensibleParser.this
    
    private[ExtensibleParser] var priority: Int = 0
    private[ExtensibleParser] var amLeftMost: Boolean = false
    override def parse[S <: T](in: Stream[S]): ParseResult[S, R] =
      if (amLeftMost && replaceLeftMost != None) {
        assert(in eq replaceLeftMost.get.remaining)
        replaceLeftMost.get match {
          case Success(remaining, r) => replaceLeftMost = None; Success(in, r: R)
          case SuccessOmit(remaining) => replaceLeftMost = None; SuccessOmit(in)
          case _ => throw new AssertionError()
        }
      }
      else
        pop.parse(in, priority)

    override def leftMost = this
    override def rightMost = this
  }
  def ref = new Reference()

  val productions = new HashMap[Int, Set[Production]]() with
                        MultiMap[Int, Production] { }
  
  override def parse[S <: T](in: Stream[S]): ParseResult[S, R] = parse(in, 0)
  
  private def parse[S <: T](in: Stream[S], minPriority: Int): ParseResult[S, R] = {
    val saveReplaceLeftMost = replaceLeftMost 
    for (prio <- TreeSet(productions.keys.toList :_*).from(minPriority))
      for (p <- productions(prio)) {
        replaceLeftMost = saveReplaceLeftMost
        p.inner.parse(in) match {
          case Failure => // pass
          case f: FailureAccept[S] => return f
          case pr: AcceptingResult[S, R] => {
            if (p.assoc == LeftAssoc &&
              p.leftMost.isInstanceOf[Reference] && p.leftMost.asInstanceOf[Reference].pop == this) {
              // left-recursive
              if (replaceLeftMost != None)
                throw new Exception("indirect recursive grammar")
                
              def parseLeft(): ParseResult[S, R] = 
                parse(replaceLeftMost.get.remaining, prio) match {
                  case Failure => replaceLeftMost.get match {
	                case Success(remaining, r) => replaceLeftMost = None; Success(remaining.asInstanceOf[Stream[S]], r)
			        case SuccessOmit(remaining) => replaceLeftMost = None; SuccessOmit(remaining.asInstanceOf[Stream[S]])
			        case _ => throw new AssertionError()
                  }
                  case pr2: AcceptingResult[T, R] => replaceLeftMost = Some(pr2); return parseLeft
                }
              
              replaceLeftMost = Some(pr)
              return parseLeft
            }
            else
              return pr
          }
        }
      }
    Failure
  }
  
  override def leftMost = this
  override def rightMost = this
}



